<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Routing',
	'<{subtitle}>' => 'Written in <span title="Communications and Networking">CS 2204</span> by <a href="https://y.st./">Alex Yst</a>, finalised on 2018-05-16',
	'<{copyright year}>' => '2018',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<h2>$a[CIDR]: Classless Internet Domain Routing</h2>
<p>
	We are given the following $a[CIDR] table and asked how packets meant for several $a[IP] addresses would be routed:
</p>
<table>
	<thead>
		<tr>
			<td>
				Address/Mask
			</td>
			<td>
				Next Hop
			</td>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>
				<code>135.46.56.0/22</code>
			</td>
			<td>
				Interface 0
			</td>
		</tr>
		<tr>
			<td>
				<code>135.46.60.0/22</code>
			</td>
			<td>
				Interface 1
			</td>
		</tr>
		<tr>
			<td>
				<code>192.53.40.0/23</code>
			</td>
			<td>
				Router 1
			</td>
		</tr>
		<tr>
			<td>
				Default
			</td>
			<td>
				Router 2
			</td>
		</tr>
	</tbody>
</table>
<p>
	Before we get started with specific destinations, it&apos;s worth taking a moment to look at what this table tells us and translating it into something we can use to determine the appropriate interface to transmit on or router to send to at a glance.
	The dividing line for <code>/22</code> is six bits into the third octet.
	<code>56</code> in binary is <code>0b00111000</code>.
	Taking the first six bits of that and allowing variance for the remaining two bits, we have a range of <code>0b00111000</code> to <code>0b00111011</code>, or <code>56</code> to <code>59</code>.
	From this, we see that <code>135.46.56.0/22</code> represents the $a[IP] addresses from <code>135.46.56.0</code> to <code>135.46.59.255</code>.
	<code>60</code> is <code>0b00111100</code> in binary.
	Again, the second address uses the same <code>/22</code> subnet size, so the last two bits may differ.
	Once more, that means the third octet may be up to three higher.
	<code>135.46.60.0/22</code> represents a range of <code>135.46.60.0</code> to <code>135.46.63.255</code>.
	Our last subnet has a network prefix of size <code>/23</code>, which leads seven bits into the third octet.
	Only the final bit of that octet is allowed to change without leaving the subnet.
	<code>40</code> in binary is <code>0b0010100</code>.
	Allowing that final bit to flip lets us use <code>41</code> as our third octet as well as <code>40</code>, so <code>192.53.40.0/23</code> represents the addresses from <code>192.53.40.0</code> to <code>192.53.41.255</code>.
</p>
<p>
	Before we build our new table, it&apos;s worth performing a quick sanity check.
	$a[CIDR] uses a longest-match method of disambiguation.
	If our longest prefix (which represents the smallest subnet) is within one of the larger subnets, we should note that in our human-readable lookup table.
	Taking a quick look though, we can see there&apos;s no overlap.
	Each range is entirely distinct.
	That leaves us with this table with which to perform lookups by hand:
</p>
<table>
	<thead>
		<tr>
			<td>
				Address/Mask
			</td>
			<td>
				Next Hop
			</td>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>
				from <code>135.46.56.0</code> to <code>135.46.59.255</code>
			</td>
			<td>
				Interface 0
			</td>
		</tr>
		<tr>
			<td>
				from <code>135.46.60.0</code> to <code>135.46.63.255</code>
			</td>
			<td>
				Interface 1
			</td>
		</tr>
		<tr>
			<td>
				from <code>192.53.40.0</code> to <code>192.53.41.255</code>
			</td>
			<td>
				Router 1
			</td>
		</tr>
		<tr>
			<td>
				everything else
			</td>
			<td>
				Router 2
			</td>
		</tr>
	</tbody>
</table>
<p>
	<code>135.46.57.14</code>, <code>135.46.63.10</code>, and <code>192.53.40.7</code> are all within ranges in the table, and will be sent to their respective interfaces or routers.
	<strong><code>135.46.57.14</code> will be sent on Interface 0, <code>135.46.63.10</code> will be sent on Interface 1, and <code>192.53.40.7</code> will be sent to Router 1.
	<code>135.46.52.2</code> and <code>192.53.56.7</code> will instead be sent to the default location, Router 2.</strong>
</p>
<h2>Assigning addresses</h2>
<p>
	The problem proposed by the assignment says that we have a block of many consecutive $a[IP] addresses, starting with <code>198.16.0.0</code>.
	Organisation B wants 2000 of them, organisation D wants 8000, and companies A and C want 4000 each.
	We are to tell how the addresses are to be divided up by specifying the starting address, ending address, and subnet mask for each organisation.
	The first thing that comes to mind though is that there are multiple solutions.
	We could put the blocks held by these companies in any order.
	Secondly, because we&apos;re specifying a mask, we can&apos;t assign addresses in a group of 10<sup>x</sup>; instead, we have to use groups of 2<sup>x</sup>.
	We&apos;re going to need to give each organisation more addresses than they&apos;ve requested.
	Organisation B will get 2048 (2<sup>11</sup>) addresses, companies A and C will get 4096 (2<sup>12</sup>) addresses, and organisation D will get 8192 (2<sup>13</sup>) addresses.
</p>
<p>
	First, let&apos;s make sure we have enough addresses to hand out.
	The assignment says we have &quot;A Large number of consecutive IP address are available starting at 198.16.0.0.&quot;.
	It doesn&apos;t say exactly how many we have, so let&apos;s assume we have the largest $a[IP] address block that could start at that address, and no further smaller blocks after it.
	<code>16</code> in binary is <code>0b00010000</code>, so we probably have the <code>198.16.0.0/12</code> block at our disposal.
	That will be far more than enough, but I like to consolidate.
	By placing our largest subnets first, we can squeeze the wasted space out from between the four needed subnets.
	This means not assigning the subnets in A, B, C, D order.
	A&apos;s and C&apos;s blocks add up to be the same size as D&apos;s block, so they can go before or after.
	Let&apos;s put them before, to keep things in mostly alphabetical order.
	B&apos;s block needs to come dead last though; otherwise, extra space between the blocks will be introduced, which would break up unused space that we might later want for larger blocks.
	Our blocks will be in the order A, C, D, B.
</p>
<p>
	A needs a block of 2<sup>12</sup> addresses.
	That means we need twelve bits for the host part of the address, leaving twenty bits for the subnet prefix.
	A will get the block at <code>198.16.0.0/20</code>.
	This is the range <code>198.16.0.0</code> to <code>198.16.15.255</code>.
	C will need to start their block at the next address, <code>198.16.16.0</code>.
	Again, their block is the same size, so they get the subnet <code>198.16.16.0/20</code>: the address range <code>198.16.16.0</code> to <code>198.16.31.255</code>.
	D&apos;s address begins at the next address, <code>198.16.32.0</code>.
	They need a block twice the size, 2<sup>13</sup> addresses, which means we need one more bit in the host portion of the address and one less in the subnet portion.
	That gives us the mask <code>198.16.32.0/19</code>, which corresponds to the range <code>198.16.32.0</code> to <code>198.16.63.255</code>.
	B&apos;s block doesn&apos;t fit nicely with the others, being the only block that small (2<sup>11</sup> addresses), so we just tack it on at the end.
	They can have <code>198.16.64.0/21</code>, the addresses from <code>198.16.64.0</code> to <code>198.16.71.255</code>.
	Formatting that as a table and putting the companies back in alphabetical order, we are left with this:
</p>
<table>
	<thead>
		<tr>
			<th>
				Organisation
			</th>
			<th>
				Starting address
			</th>
			<th>
				Ending address
			</th>
			<th>
				Subnet mask
			</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>
				A
			</td>
			<td>
				<code>198.16.0.0</code>
			</td>
			<td>
				<code>198.16.15.255</code>
			</td>
			<td>
				<code>198.16.0.0/20</code>
			</td>
		</tr>
		<tr>
			<td>
				B
			</td>
			<td>
				<code>198.16.64.0</code>
			</td>
			<td>
				<code>198.16.71.255</code>
			</td>
			<td>
				<code>198.16.64.0/21</code>
			</td>
		</tr>
		<tr>
			<td>
				C
			</td>
			<td>
				<code>198.16.16.0</code>
			</td>
			<td>
				<code>198.16.31.255</code>
			</td>
			<td>
				<code>198.16.16.0/20</code>
			</td>
		</tr>
		<tr>
			<td>
				D
			</td>
			<td>
				<code>198.16.32.0</code>
			</td>
			<td>
				<code>198.16.63.255</code>
			</td>
			<td>
				<code>198.16.32.0/19</code>
			</td>
		</tr>
	</tbody>
</table>
<h2>Distance-vector table updates</h2>
<p>
	We are given a distance-vector table for router R0 and an updated list of cost sent from router R1 to R0, and asked to apply this update.
	The cost of the R0 to R1 link is itself said to be <code>1</code>.
	This is the previous distance-vector table for R0:
</p>
<table>
	<thead>
		<tr>
			<th>
				Destination
			</th>
			<th>
				Cost
			</th>
			<th>
				Next hop
			</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>
				A
			</td>
			<td>
				<code>2</code>
			</td>
			<td>
				R1
			</td>
		</tr>
		<tr>
			<td>
				B
			</td>
			<td>
				<code>3</code>
			</td>
			<td>
				R2
			</td>
		</tr>
		<tr>
			<td>
				C
			</td>
			<td>
				<code>4</code>
			</td>
			<td>
				R1
			</td>
		</tr>
		<tr>
			<td>
				D
			</td>
			<td>
				<code>5</code>
			</td>
			<td>
				R3
			</td>
		</tr>
	</tbody>
</table>
<p>
	The updated costs as seen by R1 are as follows:
</p>
<table>
	<thead>
		<tr>
			<th>
				Destination
			</th>
			<th>
				Cost
			</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>
				A
			</td>
			<td>
				<code>1</code>
			</td>
		</tr>
		<tr>
			<td>
				B
			</td>
			<td>
				<code>1</code>
			</td>
		</tr>
		<tr>
			<td>
				C
			</td>
			<td>
				<code>4</code>
			</td>
		</tr>
		<tr>
			<td>
				D
			</td>
			<td>
				<code>4</code>
			</td>
		</tr>
	</tbody>
</table>
<p>
	For destination A, the entry stays the same. The previously-known cost was <code>2</code>.
	The R0 to R1 cost and the reported R1 to A cost also add up to <code>2</code>.
	Destination B&apos;s entry in the table gets updated to reflect a new cost and path.
	The previously-known path had a cost of <code>3</code>, but R1 is reporting the presence of a less-costly path.
	R0 to R1 has a cost of <code>1</code> and the reported cost of R1 to B is <code>1</code>, so the total cost of the new path is <code>2</code>.
	R1&apos;s report shows an increased cost for reaching destination C.
	We only keep one route in the table to get to each node, so we can&apos;t bring back information on shorter paths.
	We have no choice but to continue using the same path, but use the higher cost value.
	We add the R0 to R1 cost and the R1 to C cost to get the new cost value, <code>5</code>.
	Next time another node sends information on a less-costly path, we can switch to using that path instead.
	We add the cost of the R0 to R1 link to the reported cost of the R1 to D link to get <code>5</code>, the same value held in our table already.
	This is a different path than we&apos;ve been using, but according to the book, the router will ignore the report if the cost is identical (Dordal, 2014).
	In other words, R0 will favour the older-known path over the new path, given that there isn&apos;t a cost difference.
	The changes made result in the following new distance-vector table, held by R0:
</p>
<table>
	<thead>
		<tr>
			<th>
				Destination
			</th>
			<th>
				Cost
			</th>
			<th>
				Next hop
			</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>
				A
			</td>
			<td>
				<code>2</code>
			</td>
			<td>
				R1
			</td>
		</tr>
		<tr>
			<td>
				B
			</td>
			<td>
				<code>2</code>
			</td>
			<td>
				R1
			</td>
		</tr>
		<tr>
			<td>
				C
			</td>
			<td>
				<code>5</code>
			</td>
			<td>
				R1
			</td>
		</tr>
		<tr>
			<td>
				D
			</td>
			<td>
				<code>5</code>
			</td>
			<td>
				R3
			</td>
		</tr>
	</tbody>
</table>
<div class="APA_references">
	<h2>References:</h2>
	<p>
		Dordal, P. (2014). 9 Routing-Update Algorithms - An Introduction to Computer Networks, edition 1.9.10. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/routing.html"><code>https://intronetworks.cs.luc.edu/current/html/routing.html</code></a>
	</p>
	<p>
		Dordal, P. (2014). 10 Large-Scale IP Routing - An Introduction to Computer Networks, edition 1.9.10. Retrieved from <a href="https://intronetworks.cs.luc.edu/current/html/bigrouting.html"><code>https://intronetworks.cs.luc.edu/current/html/bigrouting.html</code></a>
	</p>
</div>
END
);
